Presented by Johan Tibell.

The most commonly used map (dictionary) data type in Haskell is implemented using a size balanced tree. While size balanced trees provide good asymptotic performance, their real world performance is not stellar, especially when used with keys which are expensive to compare, such as strings.

In this talk we will look at two different map implementations that use hashing to achieve better real world performance. The implementations have different performance characteristics: one provides very fast look-ups while the other trades better insert performance for somewhat slower look-ups. I will describe the design of these data structures and show some early benchmark results.

Scrap Your Zippers: A Generic Zipper for Heterogeneous Types

Michael Adams, Indiana University

Abstract

The zipper type provides the ability to efficiently edit tree-shaped data in a purely functional setting by providing constant time edits at a focal point in an immutable structure. It is used in a number of applications and is widely applicable for manipulating tree-shaped data structures.

The traditional zipper suffers from two major limitations, however. First, it operates only on homogeneous types. That is to say, every node the zipper visits must have the same type. In practice, many tree-shaped types do not satisfy this condition, and thus cannot be handled by the traditional zipper. Second, the traditional zipper involves a significant amount of boilerplate code. A custom implementation must be written for each type the zipper traverses. This is error prone and must be updated whenever the type being traversed changes.

The generic zipper presented in this talk overcomes these limitations. It operates over any type and requires no boilerplate code to be written by the user. The only restriction is that the types traversed must be instances of the Data class from the Scrap your Boilerplate framework.

Biography

Michael D. Adams will be completing his Ph.D. in Computer Science at Indiana University this summer. He has a B.S. in Computer Science, a B.S in Computer Engineering and a Minor in Mathematics from the University of Kansas.

His research interests are the implementation and construction of programming languages, compilers and software analysis tools that help programmers more easily implement, reason about, prove correct and improve the performance of their programs. This includes areas such as type systems, static analysis, control-flow analysis, compilers and optimization.

In spring 2007, he worked on the X10 language for an internship at IBM Research. In summer 2007, he worked on the Glasgow Haskell Compiler at Microsoft Research. In 2008-2010 he worked for Cadence Research on the Chez Scheme compiler.

He is an avid swing dancer and cyclist.

In this Meetup, we're going to have fun coding together, so bring your laptop if you can. Our plan is to run through coding examples from https://www.freecodecamp.org/. I'll give you a problem, you can try to solve it, then we'll work on it together. We'll be going through the JavaScript algorithms and data structures section.

You're welcome to join us and code other projects as well.

Be inspired! Knowledge Mavens